package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : P1755
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/9/18 14:14
 */
public class P1755 {
    public static void main(String[] args) {
        System.out.println(minAbsDifference(new int[]{7, -9, 15, -2}, -5));
    }

    public static int minAbsDifference(int[] nums, int goal) {

        return minAbsDifference(nums, 0, 0L, new ArrayList<>(), goal);
    }

    public static int minAbsDifference(int[] nums, int index, Long sum, List<Integer> path, int goal) {
        int result = Math.abs(goal);
        if (!path.isEmpty()) {
            result = (int) Math.min(result, Math.abs(goal - sum));
        }
        for (int i = index; i < nums.length; i++) {
            int num = nums[i];
            path.add(num);
            result = Math.min(result, minAbsDifference(nums, i + 1, sum + num, path, goal));
            path.remove(path.size() - 1);
        }
        return result;
    }
}
